/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package dataStructure;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * @author Mohamed.Azouz
 */
public class Mathematics {

    public static double power(double base, int exponent) {
        double ans = 1;
        if (exponent != 0) {
            int absExponent = exponent > 0 ? exponent : (-1) * exponent;
            for (int i = 1; i <= absExponent; i++) {
                ans *= base;
            }

            if (exponent < 0) {
                // For negative exponent, must invert
                ans = 1.0 / ans;
            }
        } else {
            // exponent is 0
            ans = 1;
        }

        return ans;
    }

    public boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int m = (int) Math.sqrt(n);
        for (int i = 3; i < m; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void Sieve(int n) {
        int arr[] = new int[n + 1];
        Boolean prime[] = new Boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = true;
        int m = (int) Math.sqrt(n + 1);
        for (int i = 2; i < m; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
        System.out.println(Arrays.toString(prime));
    }

    public static int GCD(int a, int b) {
        for (int i = Math.min(a, b); i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return i;
            }
        }
        return -1;
    }

    public static int GCD_R(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD_R(b, a % b);
    }

    public static int LCM(int a, int b) {
        return (b * a) / (GCD(a, b));
    }

    public static void main(String[] args) {
        //Sieve(100000);
//        System.out.println(GCD(2336, 1314));;
//        System.out.println(GCD_R(1314, 2336));;
//        System.out.println(LCM(2336, 1314));;
//        int[] arr = {25, 12, 10, 5, 1, 1, 1};
//        get36(arr, 36, 0, 0, new ArrayList<Integer>());
        get_Increasing_Subsequences();
        get_Dijkstra();
    }

    public static void get36(int[] arr, int t, int s, int cI, ArrayList<Integer> nums) {
        if (s > t || cI >= arr.length) {
            return;
        }
        if (s == t) {
            System.out.println(nums);
            return;
        }
        get36(arr, t, s, cI + 1, nums);
        nums.add(arr[cI]);
        get36(arr, t, s + arr[cI], cI + 1, nums);
    }

    static void get_Dijkstra() {
        final int N = 8;
        int s[] = new int[N];
        boolean vis[] = new boolean[N];
        int mat[][] = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mat[i][j] = 10000;
            }
        }

        mat[0][1] = 9;
        mat[0][5] = 14;
        mat[0][6] = 15;
        mat[1][2] = 24;
        mat[5][2] = 18;
        mat[5][4] = 30;
        mat[5][6] = 5;
        mat[6][4] = 20;
        mat[6][7] = 44;
        mat[2][4] = 2;
        mat[4][3] = 11;
        mat[4][7] = 16;
        mat[3][7] = 6;
        mat[3][2] = 6;
        mat[2][7] = 19;
        for (int i = 0; i < N; i++) {
            s[i] = 100000;
            vis[i] = false;
        }
        s[0] = 0;
        int mini = 100000;
        int index = 0;
        for (int i = 0; i < N; i++) {
            mini = 100000;

            for (int j = 0; j < N; j++) {
                if (mini > s[j] && !vis[j]) {
                    mini = s[j];
                    index = j;
                }
            }
            vis[index] = true;
            for (int k = 0; k < N; k++) {
                if (s[k] > s[index] + mat[index][k]) {
                    s[k] = s[index] + mat[index][k];
                }

            }
        }
        for (int i = 0; i < N; i++) {
            System.out.print(s[i] + "  ");
        }
        System.out.println("");
        System.out.println("FINAL : " + s[N - 1]);
        /*MAIN
         get_Dijkstra();
         */
    }

    static void get_Increasing_Subsequences() {
        int n = 8;
        int a[] = {5, 2, 8, 6, 3, 6, 9, 7};
        int b[] = new int[a.length];

        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = 0; j < n; j++) {
                System.out.println(a[i] + " > " + a[j] + " && " + max + " < " + b[j]);
                if (a[i] > a[j] && max < b[j]) {
                    max = b[j];
                }
            }
            b[i] = max + 1;
        }

        int max = -1;
        for (int i = 0; i < n; i++) {
            if (max < b[i]) {
                max = b[i];
            }
            //System.out.println(b[i]);
        }
        System.out.println(max);
    }
}
